﻿// 单调队列
public class FrontQue
{
    private LinkedList<int> deque;

    public FrontQue()
    {
        deque = new LinkedList<int>();
    }

    public void Push(int x)
    {
        while (deque.Count != 0 && deque.First.Value < x)
        {
            deque.RemoveFirst();
        }

        deque.AddFirst(x);
    }

    public int Max()
    {
        if (deque.Count == 0) return -1;
        return deque.Last.Value;
    }

    public void Del(int x)
    {
        if (deque.Count != 0 && deque.Last.Value == x)
        {
            deque.RemoveLast();
        }
    }
}
public class Solution {
    public int[] MaxSlidingWindow(int[] nums, int k)
    {
        int[] res = new int[nums.Length - k + 1];

        FrontQue frontQue = new FrontQue();
        
        // 初始数据
        for (int i = 0; i < k; i++)
        {
            frontQue.Push(nums[i]);
        }

        for (int i = 0; i < res.Length - 1; i++)
        {
            res[i] = frontQue.Max();
            frontQue.Del(nums[i]);
            frontQue.Push(nums[k + i]);
        }

        res[^1] = frontQue.Max();
        return res;
    }

    public static void Main(string[] args)
    {
        int[] nums = [1, 3, -1, -3, 5, 3, 6, 7];
        int k = 3;

        Solution solution = new Solution();
        int[] res = solution.MaxSlidingWindow(nums, k);
        foreach (int r in res)
        {
            Console.Write($"{r} ");
        }
        
    }
}